package 力扣_高阶数据结构.优先级队列;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @author zx
 * @create 2022-08-29 12:36
 */
public class 和最小的k个数对 {
    /**
     * @return 这个题代码看起开不难,但是看着题意很难写出代码,没有那个代码最复杂的容易想,感觉
     */
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<Freq> queue = new PriorityQueue<>(new Comparator<Freq>() {
            @Override
            public int compare(Freq o1, Freq o2) {
                return (o2.u + o2.v) - (o1.u + o1.v);
            }
        });
        for(int i = 0;i < Math.min(nums1.length,k);i++){
            for(int j = 0;j < Math.min(nums2.length,k);j++){
                if(queue.size() < k){
                    queue.offer(new Freq(nums1[i],nums2[j]));
                }else{
                    Freq peek = queue.peek();
                    int add = nums1[i] + nums2[j];
                    if(add > peek.u + peek.v){
                        continue;
                    }else{
                        queue.poll();
                        queue.offer(new Freq(nums1[i],nums2[j]));
                    }
                }
            }
        }
        List<List<Integer>> res = new ArrayList<>();
        for(int i = 0;i < k;i++){
            List list = new ArrayList();
            if(queue.isEmpty()) return res;
            Freq temp = queue.poll();
            list.add(temp.u);
            list.add(temp.v);
            res.add(list);
        }
        return res;
    }
    private class Freq{
        int u;
        int v;
        public Freq(int u, int v){
            this.u = u;
            this.v = v;
        }
    }
}
